原题链接1204. 错误票据
题目难度：简单
题目来源：第四届蓝桥杯省赛C++ A/B组,第四届蓝桥杯省赛Java A/B组
题目描述某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。
全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
输入格式第一行包含整数 N，表示后面共有 N 行数据。
接下来 N 行，每行包含空格分开的若干个（不大于100个）正整数（不大于100000），每个整数代表一个ID号。
输出格式要求程序输出1行，含两个整数 m,n，用空格分隔。
其中，m表示断号ID，n表示重号ID。
数据范围1≤N≤100
输入样例：12325 6 8 11 9 10 12 9
输出样例：17 9
题目分析这道题目的意思就是从随机开始的一个id序列，存在一个段号和一个重复，需要找到断号和重复的数字
这道题的难度是在数据输入的，他只告诉我们输入的...
原题链接1236. 递增三元组
题目难度：中等
题目来源：第九届蓝桥杯省赛C++ B组,第九届蓝桥杯省赛Java B组
题目描述给定三个整数数组
$A = [A_1, A_2, … A_N]$,$B = [B_1, B_2, … B_N]$,$C = [C_1, C_2, … C_N]$,
请你统计有多少个三元组 $(i, j, k)$ 满足：
$1 \le i, j, k \le N$
$A_i < B_j < C_k$
输入格式第一行包含一个整数 $N$。
第二行包含 $N$ 个整数 $A_1, A_2, … A_N$。
第三行包含 $N$ 个整数 $B_1, B_2, … B_N$。
第四行包含 $N$ 个整数 $C_1, C_2, … C_N$。
输出格式一个整数表示答案。
数据范围$1 \le N \le 10^5$,$0 \le A_i,B_i,C_i \le 10^5$
输入样例：123431 1 12 2 23 3 3
输出样例：127
题目分析这道题的意思很清楚，就是从A、B、C三个数组中选出三个数满足严格小...
原题链接1245. 特别数的和
题目难度：简单
题目来源：第十届蓝桥杯省赛C++ B组,第十届蓝桥杯省赛Java B组
题目描述小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
输入格式共一行，包含一个整数 n。
输出格式共一行，包含一个整数，表示满足条件的数的和。
数据范围$1 \le n \le 10000$
输入样例：140
输出样例：1574
题目分析这道题比较简单，就是问从1到n中包含2、0、1、9的数的和
这里数据量是很小的，是可以直接用枚举或者模拟来解决的，如果数据量非常大的话就需要用到数位DP了
这里我们可以枚举从1到n，然后再把每一位扣出来是否是2、0、1、9即可
示例代码123456789101112131415161718192021222324#include<iostream>using namespace std;int main(){ ...
原题链接1214. 波动数列
题目难度：中等
题目来源：第五届蓝桥杯省赛C++ A组,第五届蓝桥杯省赛Java A组
题目描述观察这个数列：
1 3 0 2 -1 1 -2 …
这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。
栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？
输入格式共一行，包含四个整数 n,s,a,b，含义如前面所述。
输出格式共一行，包含一个整数，表示满足条件的方案数。
由于这个数很大，请输出方案数除以 100000007 的余数。
数据范围$1 \le n \le 1000$,$-10^9 \le s \le 10^9$,$1 \le a,b \le 10^6$
输入样例：14 10 2 3
输出样例：12
样例解释两个满足条件的数列分别是2 4 1 3和7 4 1 -2。
题目分析这道题的意思很简单就是长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种
我们可以从数学角度来看，第一项假设为$x$，第二项就为$x+d_...
原题链接1212. 地宫取宝
题目难度：中等
题目来源：第五届蓝桥杯省赛C++ A/B/C组,第五届蓝桥杯省赛Java B/C组
题目描述X 国王有一个地宫宝库，是 $n \times m$ 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是 $k$ 件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 $k$ 件宝贝。
输入格式第一行 3 个整数，$n,m,k$，含义见题目描述。
接下来 $n$ 行，每行有 m 个整数 $C_i$ 用来描述宝库矩阵每个格子的宝贝价值。
输出格式输出一个整数，表示正好取 $k$ 个宝贝的行动方案数。
该数字可能很大，输出它对 $1000000007$ 取模的结果。
数据范围$1 \le n,m \le 50$,$1 \le k \...
原题链接1015. 摘花生
题目难度：简单
题目来源：《信息学奥赛一本通》
题目描述Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
数据范围1≤T≤100,1≤R,C≤100,0≤M≤1000
输入样例：123456722 21 13 42 32 3 41 6 5
输出样例：12816
题目分析这道题的意思就是要选择一条能摘到最多...
原题链接895. 最长上升子序列
题目难度：简单
题目描述给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式输出一个整数，表示最大长度。
数据范围$1 \le N \le 1000$，$-10^9 \le 数列中的数 \le 10^9$
输入样例：1273 1 2 1 8 5 6
输出样例：14
题目分析这道题目的意思很简单，就是从序列中找到一个最长的严格递增的子序列，例如样例中的结果就是，1,2,5,6
这是一个经典的DP问题，我们依旧从集合的角度来看，集合的含义就是所有以a[i]结尾的严格单调上升的子序列
从状态计算的角度来看，我们以倒数第二个位置可以取的不同的数字进行集合划分，一共有i种情况，分别是空，a[1]，a[2]一直到a[i-1]，那么对于其中任意一种情况，都可以继续进行划分，当不符合条件的时候，只需要进行排除即可
示例代码12345678910111213141516171819202122232425262728#include<iostream&...
原题链接2. 01背包问题
题目难度：简单
题目描述有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 iii 件物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 iii 件物品的体积和价值。
输出格式输出一个整数，表示最大价值。
数据范围$0 \lt N, V \le 1000$$0\lt v_i, w_i \le 1000$
输入样例123454 51 22 43 44 5
输出样例：18
题目分析这道题是非常典型的题目，有一类问题都叫背包问题，而这道题目则是最经典的01背包问题，题目的意思也很好理解，最终就是要让背包中的价值最大
这里的01的意思就是，每个物品最多只能使用1次
这里需要用到一个非常重要的分析解决问题的方法叫做动态规划（DP），而这种问题我们也称之为动态规划问题
对于动态规划来说，我们一般从两个方面来...